package com.atguigu.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 插值查找算法
 */
public class InsertSearch {

    public static void main(String[] args) {
        int arr[] = {1,2,34,55,66,66,99};
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> listFind = find(0, arr.length - 1, arr, 66,list);
        for (Integer ls : listFind) {
            System.out.println(ls);
        }
    }

    public static ArrayList<Integer> find(int left,int right,int arr[],int val,ArrayList<Integer> list){
        int mid = left + (right-left)*(val-arr[left])/(arr[right]-arr[left]);
        if (left>right || val < arr[left] || val > arr[right]){
            return list;
        }

        if (val > arr[mid]){
            find(mid +1,right,arr,val,list);
        }else if (val < arr[mid]){
            find(left,mid-1,arr,val,list);
        }else {
            list.add(mid);
            int ltemp = mid-1;
            while (arr[ltemp] == val){
                list.add(ltemp);
                ltemp--;
            }

            int rtemp = mid + 1;
            while (arr[rtemp] == val){
                list.add(rtemp);
                rtemp++;
            }

            return list;
        }

        return list;
    }
}
